The Unique Tree Structure Guarantee

Tree Reconstruction is the inverse problem of traversal: determining the unique structure of a Binary Tree given specific sequences of node visits.

Fundamental Rule: A Binary Tree structure can be uniquely reconstructed if and only if you are provided with:

In-order Traversal: Provides the boundary partition (L | Root | R).
Pre-order OR Post-order Traversal: Provides the identity of the Root (R).

Reconstruction Logic (Pre-order + In-order)

Identify Root (R): The first element in the Pre-order sequence is the Root (R).
Partition In-order: Locate R within the In-order sequence. All elements left of R form the Left Subtree (L). All elements right of R form the Right Subtree (R).
Isolate Sub-sequences: Use the lengths of the partitioned In-order sequences (L count, R count) to carve out the corresponding sub-sequences from the remaining Pre-order array.
Recurse: Apply the process recursively to the Left and Right subtrees until the sequences are empty.

Complexity & Performance

Metric	Time Complexity	Space Complexity	Notes
Reconstruction	$O(N)$	$O(N)$	Achieved by pre-processing In-order into a map for $O(1)$ index lookups.
Lookup Map Prep	$O(N)$	$O(N)$	Space is dominated by recursion stack depth and the HashMap size.

📝 Reconstruction Challenge

1. Given In-order [D,B,E,A,F,C] and Pre-order [A,B,D,E,C,F], what is the direct left child of node C?

A) D
B) E
C) F
D) A

2. Which pair of traversals is required to uniquely reconstruct a binary tree?

A) Pre-order and Post-order
B) In-order and Pre-order
C) Any two traversals
D) In-order and Level-order

3. Why is combining Pre-order and Post-order insufficient for unique reconstruction?

A) It is too computationally expensive.
B) It's impossible to identify the root node.
C) It creates ambiguity in defining subtree boundaries.
D) It only works for balanced binary trees.

4. Using Post-order and In-order traversals, how do you identify the root of any given subtree?

A) It's the first element in the Post-order sequence.
B) It's the last element in the Post-order sequence.
C) It's the middle element in the In-order sequence.
D) It's the first element in the In-order sequence.

KEY TIPS

💡 Expert Tips

The Root Finder

Use Pre-order to find the root at the first index of the current sub-sequence. Use Post-order to find it at the last index.

The Boundary Setter

Once the root is found, its position in the In-order sequence immediately defines the size and elements of the left and right subtrees.

Invalid Pairings

You cannot uniquely reconstruct a tree from only Pre-order and Post-order traversals. The lack of an In-order sequence creates ambiguity in the structure.